# -*- coding: utf-8 -*-
"""
作者: liuzaiqiang
邮箱: zaiqiangliu@163.com
地址: 新疆大学
创建时间: 2025/11/21 18:24
功能描述:通过二进制计数器的 "翻转次数" 来量化成本，最终证明多次increment的平摊成本接近 2。

平摊分析概念解释：
- 平摊分析不是求平均值，而是分析最坏情况下操作序列的平均性能（平摊分析关心的是：如果有人故意安排最坏的操作顺序，平均成本是多少？）
    1. "最坏情况下的操作序列"含义：
        不是单个操作的最坏情况
        而是整个操作序列被安排成最坏的情况
    2. "平均性能"的含义:
        在这个最坏的序列中，计算每个操作的平均成本
        不是所有可能序列的平均，而是最坏序列的平均

例子进一步说明：
    生动比喻：公交车票价系统
    传统平均值（注意：这是传统平均值，不是平摊分析）：
    # 假设公交车票价：- 平时：2元 - 节假日：10元- 一年平均：(2*300 + 10*65) / 365 ≈ 3.15元
    这告诉你"平均每次坐车花3.15元"，但没考虑你总是在节假日坐车的情况。
    平摊分析：
    # 考虑最坏情况：你总是选择在节假日坐车
    # 那么你的平均票价就是：10元
    # 平摊分析告诉你：在最坏的选择策略下，平均票价是10元

    平摊分析给出的是一个保证： 无论操作序列如何安排，总成本不会超过 平摊成本 × 操作次数。这比传统平均值更有用，因为它提供的是保证，而不是期望。
    所以，"最坏情况下操作序列的平均性能"的意思是：
    在被人为安排的最坏操作顺序中，计算每个操作的平均成本，这个成本就是性能的硬性保证。


- 单个操作可能很耗时，但一系列操作的总耗时除以操作次数很小
- 在这个例子中，单个increment操作最多可能翻转所有位（很耗时）
- 但n次操作的总翻转次数约等于2n，所以每次操作的平摊成本约等于2

核心概念总结：
1. 什么是"翻转成本"？
    每次二进制位从0变1或从1变0，都算作1次成本
    这是衡量算法"工作量"的指标
2. 为什么单个操作可能很贵？
    比如从 0111 (7) 到 1000 (8)：
    需要翻转4个位：0→1, 1→0, 1→0, 1→0
    单次成本是4
3. 为什么平摊成本只有约2？
    因为昂贵的操作（翻转多位）不频繁：
    翻转1位的操作：很频繁
    翻转2位的操作：较少
    翻转3位的操作：更少
    翻转4位的操作：很少
把总成本分摊后，每个操作平均只消耗约2次翻转。

4. 实际意义
    这解释了为什么计算机中的计数器操作很快 - 虽然偶尔需要处理进位，但长期来看平均性能很好。
    运行这个代码，你会看到详细的演示过程，理解每个二进制位是如何翻转的。


"""


class BinaryCounter:
    def __init__(self, bits=8):
        """
        初始化二进制计数器
        参数说明:
            bits: 计数器的二进制位数
                  - 8位可以表示0-255 (2^8-1)
                  - 如果超过最大值，计数器会归零
        属性说明:
            self.bits: 记录位数
            self.counter: 用整数存储当前计数值（内部用二进制处理）
            self.flip_count: 记录从开始到现在总共翻转了多少次二进制位（这就是我们的"成本"度量）
        """
        self.bits = bits  # 计数器的总位数
        self.counter = 0  # 当前计数值，初始为0 用整数存储当前计数值（内部用二进制处理）
        self.flip_count = 0  # 记录总翻转次数（真实成本）

    def increment(self):
        """
        计数器加1操作

        工作原理（二进制加法）：
        比如：011（3） + 1 = 100（4）
        过程：
          1. 从最低位（最右边）开始检查
          2. 遇到1就变成0，继续向左检查（相当于进位）
          3. 遇到0就变成1，停止

        具体步骤：
          011（当前值）
          ↓ 检查第0位（最低位）是1 → 变成0，继续
          010（临时状态）
          ↓ 检查第1位是1 → 变成0，继续
          000（临时状态）
          ↓ 检查第2位是0 → 变成1，停止
          100（最终结果）
        """
        i = 0  # 从第0位开始（最低位，最右边）

        # 循环：检查每一位，如果是1就翻转成0并继续，如果是0就跳出循环
        while i < self.bits and (self.counter & (1 << i)):
            # 条件解释：
            # i < self.bits: 确保不超出位数限制
            # (self.counter & (1 << i)): 检查第i位是否为1
            # 1 << i: 创建一个只有第i位是1的数
            # & 操作：如果counter的第i位是1，结果不为0（True）

            # 翻转第i位：从1变成0
            # ^ 是异或操作：相同为0，不同为1
            # 1 << i 只有第i位是1，其他位是0
            # counter与它异或：第i位翻转，其他位不变
            self.counter ^= (1 << i)
            self.flip_count += 1  # 记录一次翻转
            i += 1  # 检查下一位（向左移动）

        # 跳出循环的两种情况：
        # 1. 找到了一个0位（i < self.bits）
        # 2. 所有位都是1，已经超出位数限制（i >= self.bits）

        if i < self.bits:
            # 情况1：找到了一个0位，把它翻转为1
            # | 是按位或操作：有1则为1
            # 1 << i 只有第i位是1，其他位是0
            # counter与它或：第i位变成1，其他位不变
            self.counter |= (1 << i)
            self.flip_count += 1  # 记录这次翻转

    def aggregate_analysis(self, n):
        """
        聚合分析：计算n次increment操作的平摊成本

        参数:
            n: 要执行的increment操作次数

        返回:
            包含总成本和平摊成本的字典

        平摊分析数学原理：

        观察每个二进制位的翻转频率：
        - 第0位（最低位）：每次increment都翻转 → 翻转n次
        - 第1位：每2次increment翻转一次 → 翻转n/2次
        - 第2位：每4次increment翻转一次 → 翻转n/4次
        - 第3位：每8次increment翻转一次 → 翻转n/8次
        - ...
        - 第k位：每2^k次increment翻转一次 → 翻转n/2^k次

        总翻转次数 = n + n/2 + n/4 + n/8 + ...
                 = n × (1 + 1/2 + 1/4 + 1/8 + ...)
                 ≤ n × 2   （因为等比数列求和 ≤ 2）

        所以：平摊成本 = 总翻转次数 / n ≤ 2
        也就是说，每个increment操作平均只翻转约2个位
        """
        # 执行n次increment操作
        for _ in range(n):
            self.increment()

        # 总真实成本就是所有位翻转的总次数
        total_actual_cost = self.flip_count

        # 平摊成本 = 总真实成本 / 操作次数
        # 这表示每个操作平均消耗的成本
        amortized_cost = total_actual_cost / n

        return {
            "total_actual_cost": total_actual_cost,
            "amortized_cost": amortized_cost
        }


# ========== 演示和测试 ==========

def demonstrate_small_example():
    """
    演示小规模例子，帮助理解二进制翻转过程
    """
    print("=== 二进制计数器详细演示（4位计数器）===")
    print("让我们跟踪从0到8的计数过程：")
    print("")

    demo_counter = BinaryCounter(bits=4)

    print("数值\t二进制\t翻转说明")
    print("-" * 40)

    # 记录初始状态
    binary_str = format(demo_counter.counter, '04b')
    print(f"{demo_counter.counter}\t{binary_str}\t初始状态")

    # 执行8次递增
    for step in range(1, 9):
        # 记录递增前的状态
        old_value = demo_counter.counter
        old_flips = demo_counter.flip_count

        # 执行递增
        demo_counter.increment()

        # 计算本次翻转了多少位
        flips_this_step = demo_counter.flip_count - old_flips

        # 生成翻转说明
        flip_desc = []
        for i in range(4):
            old_bit = (old_value >> i) & 1
            new_bit = (demo_counter.counter >> i) & 1
            if old_bit != new_bit:
                flip_desc.append(f"位{i}({old_bit}→{new_bit})")

        binary_str = format(demo_counter.counter, '04b')
        print(f"{demo_counter.counter}\t{binary_str}\t翻转了{flips_this_step}位: {', '.join(flip_desc)}")


def explain_amortized_math():
    """
    解释平摊分析的数学原理
    """
    print("\n=== 平摊分析数学原理 ===")
    print("")
    print("每个二进制位的翻转频率：")
    print("位位置\t翻转间隔\t在n次操作中的翻转次数")
    print("-" * 50)

    n = 1000  # 假设操作1000次
    total_flips = 0

    # 计算前8位的翻转次数
    for bit_pos in range(8):
        flips = n // (2 ** bit_pos)  # 每2^bit_pos次操作翻转一次
        total_flips += flips
        print(f"位{bit_pos}\t每{2 ** bit_pos}次\t\t{flips}次")

    print("-" * 50)
    print(f"前8位总翻转次数: {total_flips}")
    print(f"操作次数: {n}")
    print(f"理论平摊成本: {total_flips / n:.2f}")
    print(f"理论最大值: 2.00")


# 主测试
print("=== 二进制计数器聚合分析 ===")
counter = BinaryCounter(bits=8)
result = counter.aggregate_analysis(1000)

print("分析结果：")
print(f"总真实成本（翻转次数）: {result['total_actual_cost']}")
print(f"操作次数: 1000")
print(f"平摊成本: {result['amortized_cost']:.2f}（理论上接近2）")
print("")

# 运行演示
demonstrate_small_example()
explain_amortized_math()

# 不同规模测试
print("\n=== 不同操作次数的平摊成本比较 ===")
print("操作次数越多，平摊成本越接近理论值2")
print("次数\t平摊成本")
print("-" * 20)

test_sizes = [10, 50, 100, 500, 1000, 5000]
for size in test_sizes:
    test_counter = BinaryCounter(bits=16)  # 用16位避免溢出
    result = test_counter.aggregate_analysis(size)
    print(f"{size}\t{result['amortized_cost']:.4f}")